<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>离散微积分与特殊计数序列</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<h2>离散微积分</h2>

<h3>差分</h3>

<p class="definition">
	设 `x_n` (`n ge 0`) 是一个数列. 定义 `x_n` 的<b>差分</b>为
	<span class="formula">
		`Delta x_n = x_(n+1) - x_n`,
	</span>
	其中 `Delta` 称为差分算子.
	定义 `x_n` 是自己的零阶差分: `x_n = Delta^0 x_n`.
	一般地, 对任意正整数 `k`, `x_n` 的 `k` 阶差分递归定义为
	<span class="formula">
		`Delta^k x_n = Delta( Delta^(k-1) x_n)`.
	</span>
	差分可以类比于微分运算.
</p>

<p class="remark">
	上面定义的差分又叫向前差分. 还可以定义向后差分与中心差分
	<span class="formula">
		`grad x_n = x_n - x_(n-1)`,
		`quad delta x_n = x_(n+1/2) - x_(n-1/2)`.
	</span>
	下文我们只讨论向前差分.
</p>

<p class="example">
	利用差分表计算 `x_n = 2 n^2 + 3 n + 1` 的各阶差分.
</p>

<div class="p solution">
	将 `x_0, x_1, x_2, cdots` 列于第一行,
	`Delta x_0, Delta x_1, cdots` 列于第二行,
	依此类推, 每个差分值写在被减数与减数的下面:
	<pre>
1   6   15  28  45  66  91  ..
  5   9   13  17  21  25  ..
    4   4   4   4   4   ..
	  0   0   0   0   ..
	</pre>
	从 3 阶差分开始, 每一行都是零.
</div>

<p class="solution">
  使用组合数进行符号计算. 将 `x_n` 改写为
  <span class="formula">
    `x_n = 4(n;2) + 5(n;1) + (n;0)`,
  </span>
  从而
  <span class="formula">
    `Delta x_n = 4(n;1) + 5(n;0)`,<br>
    `Delta^2 x_n = 4(n;0)`,<br>
    `Delta^3 x_n = 0`.
  </span>
</p>

<p>	如同微积分中我们有一张常用函数的导数表一样, 我们来推导一些常见数列的差分.</p>

<p class="proposition">
	<b>指数函数的差分公式</b>
	直接计算,
	<span class="formula">
		`Delta 2^n = 2^n`,
        `quad Delta a^n = a^n (a-1)`,
        `quad Delta^k a^n = a^n (a-1)^k`.
	</span>
	`2^n` 的差分是它自己, 这一性质对应于微积分中的 `"e"^x`.
	如果记 `H_n = sum_(k=1)^n 1/k`, 则
	<span class="formula">
		`Delta H_n = 1/(n+1)`,
	</span>
	这一性质对应于微积分中的 `ln x`.
</p>

<p class="definition">
  <b>下降幂与上升幂</b>
  设 `k` 为非负整数,
  <span class="formula">
    `n^(ul k) = prod_(0 le i lt k) (n-i) = n(n-1) cdots (n-k+1)`,<br/>
    `n^(bar k) = prod_(0 le i lt k) (n+i) = n(n+1) cdots (n+k-1)`.
  </span>
  下降幂与二项式系数只相差系数 `k!`:
  <span class="formula">
    `n^(ul k)/(k!) = (n;k)`.
  </span>
  下面考虑负指数的下降幂.  设 `k` 为正整数, 定义
  <span class="formula">
    `n^(ul(-k)) = prod_(1 le i le k) (n+i)^-1`
    `= 1/((n+1)(n+2) cdots (n+k))`.
  </span>
  特别地 `n^(ul(-1)) = 1/(n+1)`.
</p>

<p class="proposition">
  <b>下降幂的差分公式</b>
  `k` 为非负整数时, 由 Pascal 公式 `(n+1; k) = (n; k) + (n; k-1)` 知
  <span class="formula">
    `Delta (n;k) = (n; k-1)`.
  </span>
  写成下降幂形式就是
  <span class="formula">
    `Delta n^(ul k) = k n^(ul(k-1))`.
  </span>
  可以验证上式对于负指数下降幂仍成立. 因此, 下降幂的差分仍是一个下降幂,
  这对应于微分学的公式 `"d"/dx x^n = n x^(n-1)`.
  然而 `n^k` 没有简单的差分公式, 所以在离散数学的世界里,
  用下降幂代替普通的幂, 往往能简化计算.
</p>

<table>
  <caption>常见函数的差分</caption>
  <tr>
    <td>`f(n)`</td>
    <td>`Delta f(n)`</td>
    <td>`f(n)`</td>
    <td>`Delta f(n)`</td>
  </tr>
  <tr>
    <td>`2^n`</td>
    <td>`2^n`</td>
    <td>`a^n`</td>
    <td>`a^n(a-1)`</td>
  </tr>
  <tr>
    <td>`(n;k)`</td>
    <td>`(n;k-1)`</td>
    <td>`n^(ul k)`</td>
    <td>`k n^(ul(k-1))`</td>
  </tr>
  <tr>
    <td>`H_n`</td>
    <td>`n^(ul(-1))`</td>
  </tr>
</table>

<h3>求和</h3>

<ol class="proposition">
  <li>如同积分与微分一样, <b>求和与差分具有线性性</b>:
    <span class="formula">
      `sum (a x_n + b y_n) = a sum x_n + b sum y_n`,
      `quad Delta (a x_n + b y_n) = a Delta x_n + b Delta y_n`.
    </span>
  </li>
  <li>如同积分与微分互逆一样, <b>求和与差分互为逆运算</b>:
    <span class="formula">
      `sum_(0 le k lt n) Delta x_k = [x_k]_0^n = x_n - x_0`,
      `quad Delta sum_(0 le k lt n) x_k = x_n`.
    </span>
    特别当 `x_0 = 0` 时, 两式结果相等.
  </li>
  <li>
    <b>分部求和公式 (Abel 变换)</b>
    因为
    <span class="formula">
      `Delta x_k y_k = x_(k+1) y_(k+1) - x_k y_(k+1) + x_k y_(k+1)
      - x_k y_k`
      `= y_(k+1) Delta x_k + x_k Delta y_k`,
    </span>
    所以
    <span class="formula">
      `sum_(0 le k lt n) x_k Delta y_k`
      `= [x_k y_k]_0^n - sum_(0 le k lt n) y_(k+1) Delta x_k`.
    </span>
    分部求和的几何意义见下图: 左上阶梯形 (蓝) = 大矩形 - 左下小矩形 (黄) - 右下阶梯形 (红).
  </li>
</ol>

<div class="img md">
  <img src="../img/sum-by-part.svg">
</div>

<p class="example">
  求 `sum k 2^k`, 其中求和范围是 `0 le k lt n`.
</p>

<p class="solution">
  <span class="formula">
    `sum k 2^k = sum k Delta 2^k = [k 2^k]_0^n - sum 2^(k+1) Delta k`
    `= n 2^n - 2 sum Delta 2^k = n 2^n - 2 [2^k]_0^n`
    `= n 2^n - 2(2^n - 1)`.
  </span>
</p>

<p class="example">
  求 `sum H_k`, 求和范围是 `0 le k lt n`.
</p>

<p class="solution">
  <span class="formula">
    `sum H_k = sum H_k Delta k = [k H_k]_0^n - sum (k+1) Delta H_k`
    `= n(H_n - 1)`.
  </span>
</p>

<p class="example">
  应用离散微积分的方法导出朱世杰恒等式:
  <span class="formula">
    `sum_(k=0)^n (k;p)`
    `= sum_(k=0)^n Delta (k; p+1)`
    `= (n+1; p+1) - (0; p+1)`
    `= (n+1; p+1)`.
  </span>
</p>

<p class="example">
  使用下降幂的差分求 `sum_(k=1)^n k^2`, `sum_(k=1)^n k^3`.
</p>

<ol class="solution">
  <li>
    <span class="formula">
      `sum_(k=1)^(n-1) k^2`
      `= sum k + sum k (k-1)`
      `= (n(n-1))/2 + (n(n-1)(n-2))/3`
      `= (n(n-1)(2n-1))/6`.
    </span>
  </li>
  <li>
    <span class="formula">
      `sum_(k=1)^(n-1) k^3`
      `= sum k + 3sum k^(ul 2) + sum k^(ul 3)`
      `= n^(ul 2)/2 + n^(ul 3) + n^(ul 4)/4`
      `= ((n(n-1))/2)^2`.
    </span>
  </li>
</ol>

<h3>几个公式</h3>

<p>本节的最后导出几个有用的公式.</p>

<p class="theorem">
  <b>组合反演公式</b>
  关于数列 `{x_n}, {y_n}`, 若
  <span class="formula">
    `y_n = sum_(k=0)^n (n;k) x_k`,
  </span>
  则
  <span class="formula">
    `x_n = sum_(k=0)^n (n;k) (-1)^(n-k) y_k`.
  </span>
  如果记 `x_n = x^n`, `y_n = y^n`, 以上结论形式地记为
  <span class="formula">
    `y^n = (x+1)^n` `rArr x^n = (y-1)^n`.
  </span>
  或对称地,
  <span class="formula">
    `y^n = (1-x)^n` `rArr x^n = (1-y)^n`.
  </span>
</p>

<p class="proof">
  代入验证,
  <span class="formula">
    `sum_(k=0)^n (n;k) (-1)^(n-k) sum_(j=0)^k (k;j) x_j`
    `= sum_(j=0)^n x_j sum_(k=j)^n (n;k)(k;j) (-1)^(n-k)`
    `= sum_(j=0)^n x_j A_j`.
  </span>
  其中
  <span class="formula">
    `A_j = sum_(k=0)^(n-j) (n;k)(n-k;j) (-1)^k`
    `= sum_(k=0)^(n-j) (n;j)(n-j;k) (-1)^k`
    `= (n;j) (1-1)^(n-j)`
    `= {1, if j = n; 0, if j lt n:}`
  </span>
  因此 `sum_(j=0)^n x_j A_j = x_n`.
</p>

<p class="theorem">
  <b>`k` 阶差分公式</b>
  <span class="formula">
    `Delta^k x_n = sum_(j=0)^k (k;j) (-1)^(k-j) x_(n+j)`.
  </span>
  如果记 `x_n = x^n`, 上式形式地写为
  <span class="formula">
    `Delta^k x^n = (x-1)^k x^n`, 亦即 `Delta = x - 1`.
  </span>
  该表达式与指数函数的 `k` 阶差分一致.<br>
  反演得到<b>离散 Maclaurin 公式</b>:
  <span class="formula">
    `x_(n+k) = sum_(j=0)^k (k;j) Delta^j x_n`
    `= sum_(j=0)^k (Delta^j x_n)/(j!) k^(ul j)`.
  </span>
  形式记为
  <span class="formula">
    `x^(n+k) = (Delta+1)^k x^n`, 亦即 `x = Delta + 1`.
  </span>
  向后差分、中心差分也有类似的表达式.
</p>

<p class="proof">
  `k = 0` 时, `Delta^0 x_n = x_n` 成立; 假设等式对 `k-1` 成立, 则
  <span class="formula align">
    `Delta^k x_n = Delta^(k-1) x_(n+1) - Delta^(k-1) x_n`<br>
    `= sum_(j=0)^(k-1) (k-1; j) (-1)^(k-1-j) x_(n+1+j)`
    `- sum_(j=0)^(k-1) (k-1; j) (-1)^(k-1-j) x_(n+j)`<br>
    `= x_(n+k) - (-1)^(k-1) x_n`
    `+ sum_(j=1)^(k-1) (-1)^(k-j) x_(n+j) ((k-1; j-1) + (k-1; j))`<br>
    `= sum_(j=0)^k (k;j) (-1)^(k-j) x_(n+j)`.
  </span>
</p>

<p class="theorem">
  <b>离散 Maclaurin 公式</b>
  设 `x_n` 为数列通项, `m` 为非负整数, 且对任意 `k gt m` 有
  `Delta^k x_0 = 0`, 则
  <span class="formula">
    `x_n = sum_(k=0)^m (n;k) Delta^k x_0`
    `= sum_(k=0)^m (Delta^k x_0)/(k!) n^(ul k)`.
  </span>
</p>

<p class="proof">
  首先由大于 `m` 阶的差分都等于零知, `x_n` 是关于 `n` 的多项式.<br/>
  因为 `(n; k)` 是关于 `n` 的 `k` 次多项式, `k = 0, 1, cdots, m`, 所以
  `(n;k)` 线性无关, 它们组成多项式空间 `bbb P{::}_m[x]` 的基.<br/>
  下面计算 `(n;k)` 的差分.
  因为 `Delta_n (n;k) = (n;k-1)`, 所以
  <span class="formula">
    `{: Delta_n^j (n;k) |_(n=0) = {: (n; k-j) |_(n=0)`
    `= delta_(j k) = { 1, if j = k; 0, if j != k :}`.
  </span>
  现在将多项式 `x_n` 用基底线性表示为
  <span class="formula">
    `x_n = sum_(k=0)^m c_k (n; k)`,
  </span>
  则由差分的线性性知,
  <span class="formula">
    `Delta_n^j x_0 = sum_(k=0)^m c_k {:Delta_n^j (n;k)|_(n=0)`
    `= sum_(k=0)^m c_k delta_(j k)`
    `= c_j`.
  </span>
  所以公式成立.
</p>

<p class="theorem">
  <b>带余项的离散 Maclaurin 公式</b>
  <span class="formula">
    `x_n = sum_(k=0)^m (n;k) Delta^k x_0 + R_m(n)`,
  </span>
  其中 `R_m(n) = sum_(0 le k lt n) (n-k-1; m) Delta^(m+1) x_k`.
</p>

<p class="proof">
  设 `m gt 0`, 对 `R_m(n)` 分部求和,
  <span class="formula">`{:
    R_m(n) ,= sum_(0 le k lt n-1) (n-k-1; m) Delta^(m+1) x_k;
    ,= [(n-k-1; m) Delta^m x_k]_(k=0)^(n-1)
    + sum_(0 le k lt n-1) (n-k-2; m-1) Delta^m x_(k+1);
    ,= -(n-1; m) Delta^m x_0 + sum_(1 le k lt n) (n-k-1; m-1)
    Delta^m x_k;
    ,= -(n-1; m) Delta^m x_0 - (n-1; m-1) Delta^m x_0 + sum_(0 le k lt
    n) (n-k-1; m-1) Delta^m x_k;
    ,= -(n; m) Delta^m x_0 + R_(m-1) (n).:}`
  </span>
  于是
  <span class="formula">
    `R_0(n) = sum_(1 le k le m) (R_(k-1)(n) - R_k(n)) + R_m(n)`,
  </span>
  即
  <span class="formula">
    `x_n - x_0 = sum_(1 le k le m) (n;k) Delta^k x_0 + R_m(n)`.
  </span>
</p>

<h2>Stirling 数</h2>

<p class="definition">
	<b>Stirling 数</b>
	从线性代数的角度, `{x^k}_(k=0)^n` 与 `{x^(ul k)}_(k=0)^n`
	是次数不超过 `n` 的多项式组成的线性空间 `bbb P{::}_n[x]` 的两个基底.
	为了方便离散微积分运算, 需要将多项式的基由普通幂换为由下降幂.
	下面定义的两类 Stirling 数分别给出了两组基底之间互化的系数
	(即过渡矩阵):
	<span class="formula">
		`x^(ul n) = sum_(k=0)^n (-1)^(n-k) s(n, k) x^k`,
		`quad x^n = sum_(k=0)^n S(n, k) x^(ul k)`.
	</span>
	其中 `s(n, k)` 称为<b>第一类 Stirling 数</b>,
	`S(n, k)` 称为<b>第二类 Stirling 数</b>.
</p>

<pre>
          1
        0   1
      0   1   1
    0   1   3   1
  0   1   7   6   1
0   1  15  25  10   1
</pre>

<p class="proposition">
  <b>递推公式</b>
  <span class="formula">
    `S(n, k) = {
      1, if n = k;
      0, if n gt 0 and k = 0;
      S(n-1, k-1) + k S(n-1, k), otherwise;
    :}`
  </span>
</p>

<p class="proof">
  从定义式 `x^n = sum_(k=0)^n S(n, k) x^(ul k)` 出发.
  考虑两边的 `n` 次项系数和常数项分别可得 `S(n, n) = 1` (`n ge 0`) 和
  `S(m, 0) = 0` (`m gt 0`). 现在设 `n gt 0`, 两边对 `x` 差分得到
  <span class="formula">
    `(x+1)^n - x^n = sum_(k=1)^n S(n, k) k x^(ul (k-1))`.
  </span>
  另一方面
  <span class="formula align">
    `(x+1)^n - x^n`
    `= 1/(x+1) (x+1)^(n+1) - x^n`<br>
    `= 1/(x+1) sum_(k=1)^(n+1) S(n+1, k) (x+1)^(ul k)`
    `- sum_(k=1)^n S(n, k) x^(ul k)`<br>
    `= sum_(k=1)^(n+1) S(n+1, k) x^(ul(k-1))`
    `- sum_(k=2)^(n+1) S(n, k-1) x^(ul(k-1))`<br>
    `= sum_(k=1)^n S(n+1, k) x^(ul(k-1))`
    `- sum_(k=1)^n S(n, k-1) x^(ul(k-1))`.<br>
  </span>
  比较得
  <span class="formula">
    `k S(n, k) = S(n+1, k) - S(n, k-1)`.
  </span>
</p>

<p class="proposition">
  <b>通项公式</b>
  <span class="formula">
    `S(n,k) = 1/k! sum_(j=0)^k (k;j) (-1)^j (k-j)^n`.
  </span>
  令 `S^k = k^n`, 上式形式写为 `k! S(n, k) = (S-1)^k`.
</p>

<p class="proof">
  只需验证这个通项公式适合边界条件和递推公式, 过程略.
</p>

<p class="proof">
  在定义式 `x^n = sum_(k=0)^n S(n, k) x^(ul k)` 中, 考虑数列 `1^n, 2^n,
  3^n, cdots, n^n`, 由离散 Maclaurin 公式和 `k` 阶差分公式
  <span class="formula">
    `S(n,k) = 1/k! {:Delta_x^k x^n|_(x=0)`
    `= 1/k! sum_(i=0)^k (k;j) (-1)^j (k-j)^n`.
  </span>
</p>

<p class="proposition">
  <b>组合意义</b>
  `n` 元集到 `k` 元集的满射数等于 `k! S(n, k)`.
  换言之, 将 `n` 元集划分为 `k` 份, 每份不空的方法数为 `S(n, k)`.
</p>

<p class="proof">
  应用容斥原理, `n` 元集到 `k` 元集的满射数目等于全部映射 `k^n`,
  减去有一个元素无原像的情形 `(k;1) (k-1)^n`,
  再加上有两个元素无原像的情形 `(k;2) (k-2)^n`,
  再减去有三个元素无原像的情形... 最终得到
  <span class="formula">
    `sum_(j=0)^k (k;j) (-1)^j (k-j)^n = k! S(n, k)`.
  </span>
</p>

<ol class="proof">
  假设将 `n` 元集划分为 `k` 份, 每份不空的方法数为 `T(n, k)`,
  下证 `T(n, k)` 和 `S(n, k)` 满足相同的递推公式, 从而 `T(n, k) = S(n, k)`.
  事实上, 显然有 `T(n, n) = 1`, `T(n, 1) = 1`.
  接下来考虑 `n` 元集中的固定元素 `x_0`,
  <li>若 `x_0` 在划分中独占一份 (住单人间, 没有室友),
    只需再将剩下的 `n-1` 个元素分为 `k-1` 份, 方法数为 `T(n-1, k-1)`;
  </li>
  <li>若 `x_0` 在划分中不是独占一份, 只需将剩下的 `n-1` 个元素分为 `k` 份,
    然后选择一份将 `x_0` 加入其中 (选择一个房间入住), 方法数为 `k T(n-1, k)`.
  </li>
  综上 `T(n, k) = T(n-1, k-1) + k T(n-1, k)`, 恰好满足 `S(n, k)` 的递推公式.
</ol>

<p class="proof">
  `n` 元集到 `k` 元集的映射, 相当于 `n` 元集到 `j` 元集的满射总和, `j = 0, 1, cdots, k`:
  <span class="formula">
    `k^n = sum_(j=0)^k (k;j) S'(n, j)`,
  </span>
  反演得
  <span class="formula">
    `S'(n, k) = sum_(j=0)^k (k;j) (-1)^(k-j) j^n`,
  </span>
  因此 `S'(n, k) = k! S(n, k)`.
</p>

<p class="proposition">
	<b>等幂求和</b>
	记 `(:n;k:) = S(n,k) k!`, `S_n(x) = sum_(i=1)^x i^n`.  则
	<span class="formula">
		`S_n(x) = sum_(k=0)^n (:n;k:) (x+1; k+1)`, `quad n ge 1`.
	</span>
	关于第一类和第二类 Bernoulli 数, 分别有
	<span class="formula">
		`B_n^(-) = sum_(k=0)^n (:n;k:) (-1)^k/(k+1)`, `quad n ge 0`,<br/>
		`B_n^(+) = sum_(k=0)^n (:n;k:) (-1)^(k-1)/(k(k+1))`, `quad n ge
		1`.
	</span>
</p>

<p class="proof">
	由第二类 Stirling 数定义
	<span class="formula">
		`i^n = sum_(k=0)^n (:n;k:) (i;k)`,
	</span>
	两边令 `i` 从 `0` 到 `x` 求和就得到第一式.
	再和 Bernoulli 数的公式
	<span class="formula">
		`S_n(x) = 1/(n+1) sum_(k=0)^n (n+1;k) B_k^(+) x^(n+1-k)`
	</span>
	比较一次项系数, 就得到 `B_n^(+)` 的表达式.
	同理比较
	<span class="formula">
		`S_n(x-1) = sum_(k=0)^n (:n;k:) (x;k+1)`, `quad n ge 1`,<br>
		`S_n(x-1) = 1/(n+1) sum_(k=0)^n (n+1;k) B_k^(-) x^(n+1-k)`,
		`quad n ge 1`
	</span>
	的一次项系数得
	<span class="formula">
		`B_n^(-) = sum_(k=0)^n (:n;k:) (-1)^k/(k+1)`, `quad n ge 1`.
	</span>
	容易验证上式对 `n=0` 也成立.
</p>

<h2>Euler 数</h2>

<p class="definition">
  <b>Euler 数</b> 对正整数 `n` 和 正整数 `k le n`,
  <span class="formula">
    `A_(n, k) = {
      1, if n = 1 or k = n;
      (n-k+1) A_(n-1,k-1) + k A_(n-1, k), otherwise;
    :}`
  </span>
  表示 `1~n` 的排列中, 恰有 `k-1` 个相邻逆序对的排列数.
  比如 `1, 3, 5, 4, 2` 中, `(5, 4)`, `(4, 2)` 是两个相邻逆序对.
  由定义 `sum_(k=1)^n A_(n, k) = n!`.
</p>

<pre>
          1
        1   1
      1   4   1
    1  11  11   1
  1  26  66  26   1
1  57 302 302  57   1
</pre>

<p class="proposition">
  [来自 诗许] 多项式的基底表示
  <span class="formula">
    `x^n = sum_(k=1)^n (x+k-1; n) A_(n, k)`.
  </span>
  此公式两边对 `n` 求和即得到又一个等幂求和公式.
</p>

<p class="proof">
  归纳证明. `n = 1` 时 `x = (x+1-1; 1) A_(1, k)` 成立.
  假设命题对 `n` 成立, 考虑 `n+1` 的情形:
  <span class="formula align">
    `sum_(k=1)^(n+1) (x+k-1; n+1) A_(n+1, k)`<br>
    `= (x; n+1) + (x+n; n+1)`
    `+ sum_(k=2)^n (x+k-1; n+1)[(n-k+2) A_(n,k-1) + k A_(n, k)]`<br>
    `= (x; n+1) + (x+n; n+1)`
    `+ sum_(k=1)^(n-1) (x+k; n+1) (n-k+1) A_(n,k) + sum_(k=2)^n (x+k-1; n+1) k A_(n,k)`<br>
    `= (x; n+1) + (x+n; n+1) + (x+1; n+1) n + (x+n-1; n+1) n`
    `+ sum_(k=2)^(n-1) A_(n,k) (x+k-1; n)((x+k)(n-k+1)
    + k(x+k-n-1))/(n+1)`<br>
    `= sum_(k=1)^n A_(n, k) (x+k-1; n) x`<br>
    `= x^(n+1)`.
  </span>
</p>

<p class="proposition">
  Euler 数的显式表达式为
  <span class="formula">
    `A_(n, k) = sum_(j=0)^k (n+1; j) (-1)^j (k-j)^n`.
  </span>
</p>

<div class="p proof">
  直接代入递推式验证:
  <span class="formula">
    `A_(n, 1) = (n+1; 0) 1^n - (n+1; 1) 0^n = 1`,<br>
    `A_(n, n) = sum_(j=0)^n (-1)^j (n+1; j) (n-j)^n = 1`.<sup>[注]</sup>
  </span>
  且
  <span class="formula align">
    `(n-k+1) A_(n-1, k-1) + k A_(n-1, k)`<br>
    `= -(n-k+1) sum_(j=1)^k (-1)^j (n; j-1) (k-j)^(n-1)`
    `+ k^n + k sum_(j=1)^k (-1)^j (n;j) (k-j)^(n-1)`<br>
    `= k^n - sum_(j=1)^k (-1)^j (n+1)(n; j-1) (k-j)^(n-1)`
    `+ sum_(j=1)^k (-1)^j k (n+1; j) (k-j)^(n-1)`<br>
    `= sum_(j=0)^k (-1)^j (n+1; j) (k-j)^n`<br>
    `= A_(n, k)`.
  </span>
  <hr>
  <b>注</b> [来自 破壁人五号] 记 `x_k = k^n`, 因为它是 `n` 次多项式,
  故它在原点的 `n+1` 阶差分为零, 即
  <span class="formula">
    `Delta^(n+1) x_0 = sum_(j=0)^(n+1) (n+1;j) (-1)^j (n-j)^n = 0`,
  </span>
  从而 `A_(n,n) = 1`.
</div>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
